package bTree.LeetCode;

public class 设计链表 {

    class Node{
        int val;
        Node next;
        Node pre;
    }
    Node head;
    Node tail;
    int cnt=-1;
    public MyLinkedList() {
        head=new Node();
        tail=new Node();
        head.next=tail;
        tail.pre=head;
    }

    public int get(int index) {
        if (index>cnt){
            return -1;
        }
        Node p=head;
        int point=-1;
        while (p!=tail){
            if (point==index){
                return p.val;
            }else {
                point++;
                p=p.next;
            }
        }
        return -1;
    }

    public void addAtHead(int val) {
        Node next = head.next;
        Node node = new Node();
        node.val=val;
        head.next=node;
        node.pre=head;
        node.next=next;
        next.pre=node;
        cnt++;
    }

    public void addAtTail(int val) {
        Node pre = tail.pre;
        Node node = new Node();
        node.val=val;
        pre.next=node;
        node.pre=pre;
        node.next=tail;
        tail.pre=node;
        cnt++;
    }

    public void addAtIndex(int index, int val) {
        int i=-1;
        if (index>cnt+1){
            return;
        }
        Node p=head;
        while (true){
            if (i==index){
                Node node = new Node();
                node.val=val;
                node.pre=p.pre;
                p.pre.next=node;
                node.next=p;
                p.pre=node;
                cnt++;
                break;
            }else {
                i++;
                p=p.next;
            }
        }
    }

    public void deleteAtIndex(int index) {
        int i=-1;
        if (index>cnt){
            return;
        }
        Node p=head;
        while (true){
            if (i==index){
                p.pre.next=p.next;
                p.next.pre=p.pre;
                cnt--;
                break;
            }else {
                i++;
                p=p.next;
            }
        }
    }
}

/**
 * Your MyLinkedList object will be instantiated and called as such:
 * MyLinkedList obj = new MyLinkedList();
 * int param_1 = obj.get(index);
 * obj.addAtHead(val);
 * obj.addAtTail(val);
 * obj.addAtIndex(index,val);
 * obj.deleteAtIndex(index);
 */